Conventionally, for instance, as described in the below-mentioned patent publication 1, while a car navigation device holds map data, the car navigation device executes a map matching operation in a time interval of, for example, 1 second in order to identify a position of a traveling vehicle on the map data. In this map data, all of roads whose widths are wider than, or equal to 3.3 m have been stored. The car navigation device executes a map matching operation while map data of an area (normally, square of approximately several hundreds meters) which is limited to an area around the own vehicle position is employed as an object area, and thus, acquires such a point on the map, which corresponds to the own vehicle position.
As map matching methods, several sorts of map matching methods are known. For instance, an algorithm of a macro map matching operation is defined as follows:
(1) As shown in FIG. 35(a), while a vehicle position acquired by a GPS receiver is used as a WP (way point) corresponding to a point which is formed on a shape vector, links located in a peripheral area of the WP are searched so as to detect a link having such azimuth within a square made of A meters (on the order of 250 meters) where a first way point WP1 is set to a center thereof. The azimuth of this link is defined by that a difference between this azimuth and traveling azimuth of the vehicle is limited in +B degrees to −B degrees (for example, B is nearly equal to 45 degrees). Then, this detected link is set to a candidate point (symbol “X”). It is so assumed that a total link number (n) of the candidate points is selected to be 5 to 8 pieces. In FIG. 35(b), candidate points of the first way point WP1 are set to 1-1, 1-2, 1-3.
(2) As indicated in FIG. 35(b), a link having such azimuth is detected within the square made of A meters where a next WP2 is set to a center thereof. The azimuth of this link is defined by that a difference between this azimuth and traveling azimuth of the vehicle is limited in +B degrees to −B degrees. “n” pieces of links are set as candidate points (2-1, 2-2, 2-3).
(3) This process operation is repeatedly carried out until the matching operation is reached to a final WP.
(4) The respective candidate points are connected to each other along the road links so as to form a shape pattern. In such a case that candidate points are not connected along a road (for instance, candidate points 3-3 and 3-2 of WP3 cannot be connected to candidate point of next WP4 along road), a shape pattern is not formed.
(5) While the respective shape patterns are compared with the shapes of WP1, WP2, - - - , one shape pattern is selected which is mostly resembled to the shapes of the way points. Namely, this shape pattern is located near the way points, and owns a small fluctuation with respect to the shapes of WP1, WP2, - - - , which are evaluated by standard deviation, or the like.
Assuming now that a total number of WPs is equal to “M” pieces and “N” pieces of candidate points per each of WPs are obtained as an average value, the shape patterns which are acquired in the item (4) are combinations of N M pieces, normally become several thousands through several ten-thousands of shape patterns.
On the other hand, the Inventor of the present invention has proposed the traffic information transfer system using the map matching operation (Japanese Patent Application No. 2002-89069). In this system, while a status amount (travel time, and traffic jam degree etc.) of traffic information which is changed along a road is expressed by a function of a distance measured from a reference node of a shape vector which indicates the road, both data of this traffic information and data of a shape vector indicative of a road shape are provided to a user terminal. The user terminal executes a map matching operation by using the shape vector so as to identify a objective road of the traffic information, and reproduces the traffic information on this road from the data of the traffic information.
FIG. 36(b) shows data of traffic information which is transferred in this system, and FIG. 36(a) represents shape vector data of roads which are transferred in combination with this traffic information data. Alternatively, these data may be coded so as to compress data amounts. FIG. 37(a) and FIG. 37(b) shows both shape vector data which have been coded, and traffic information data. After the user terminal which has received these data decodes both shape vector data and traffic information data, the user terminal similarly performs a map matching operation while the respective nodes contained in the shape vector data are defined as WPs so as to identify a objective road of the traffic information, and reproduces the traffic information on the objective road from the traffic information data.
In the presently available traffic information, while unified numbers are applied to nodes and links, a objective road is identified by this number. In this case, in connection with newly constructing operations of reads and route changes, updating operations as to node numbers and link numbers are required. Since newly constructing operations of roads and route changes are not stopped in future, the method for using the unified numbers necessarily requires work loads of maintenance. To the contrary, since the road position is identified by the map matching operation in this traffic information transfer system, such unified numbers need not be applied to the nodes and the links, and thus, the work loads can be reduced.
[Patent Publication 1]
Japanese Laid-open Patent Application No. HEI-7-260499
However, in this traffic information transfer system, the reception-sided device (decoder: navigation device etc.) must execute the map matching operation with respect to the long subject section within the wide range (for example, entire area of wards in TOKYO, or square made of 10 Km) which is contained in the traffic information.
Also, in the process operation of the map matching operation, in such a case that the above-described WPs are used which are employed so as to identify the vehicle position, when a large number of candidate points are formed around the WPs, a very long time is necessarily required to execute the retrieving process operations (namely, process operations (1) and (2) of above-described macro map matching operations) for the candidate points. This process time is increased directly proportional to a total number of WPs. Also, combinations among the respective candidates points are exponentially increased in response to a total number of the candidate points and a total number of the WPs, and thus, the forming process operation (above-described process operation (4)) of the shape pattern and the comparing process operation (above-described process operation (5)) require a plenty of time.
As a result, there is an object to shorten the processing time for the map matching operation.
Also, in such a probe acquisition system that drive data of vehicles (probes) which are driven in various places are acquired by a center so as to be utilized to form traffic information, positional data indicative of drive loci are collected from a large number of probes to one center. Then, this center identifies roads along which the respective probes are driven by executing map matching operations based upon the positional data. As a consequence, a high-speed map matching operation is required in order that the data collected from a large number of probes can be quickly processed.
Also, vehicles which mount car navigation machines are rapidly increased. In an on-vehicle navigation system which is used by this car navigation machine, while a digital map database is held, maps around the own vehicle position can be displayed on a screen, and in addition, travel loci and route searching results up to a destination place can be displayed on the maps based upon latitude/longitude data received by a GPS receiver.
It should be noted that digital map databases may contain errors due to a fatal aspect of reduced scale maps. While degrees of errors are different from each other depending upon digital map databases, there are, for instance, commercially-available digital map databases having a reduced scale of 1/25000 which contain an error of approximately 50 meters in accordance with places.
Also, in this on-vehicle navigation machine, such traffic information as traffic jam information and traffic accident information is received which is provided from a traffic information providing system, and then, a traffic jam place and a traffic accident position may be displayed on a map, and/or a route searching operation is carried out by adding these traffic jam/accident information to a condition.
In the above-described traffic information providing system, as represented in FIG. 57, traffic information is supplied from a control center 71 which controls a regional area to a traffic information distribution center 72, and then, traffic information which has been edited for purposes of various media (FM broadcast, on-road beacon, portable telephones, and the like) is transmitted via these various media. It should also be understood that the control center 71 communicates the traffic information with a control center 78 of another regional area, and thus, acquires traffic information within a wide zone which contains a peripheral area.
As to the traffic information supplied by the above-explained traffic information providing system, for example, in such a case that latitude/longitude data as to a traffic jam position and a traffic accident position is solely provided in order to inform the traffic jam position and the traffic accident position, there is a risk that if both a traffic information providing source and a traffic information provided destination employ different sorts of digital map databases, then the on-vehicle navigation machine identifies a different position on a road as the traffic accident position. This is because, as previously explained, digital map databases held by on-vehicle navigation machines own errors which are different from each other, depending upon sorts of these digital map databases.
In order to improve an incorrectness of such information transfer operations, or information display operations, on-vehicle navigation systems employ such map information shown in FIG. 58. As indicated as one example in FIG. 58(a), assuming now that intersections “a” and “b” of a road network correspond to nodes and a road “c” between the nodes corresponds to a link, node numbers (a=1111, b=3333) are set to the respective nodes, which exclusively represent these nodes, whereas a link number (c =11113333) is set to the respective links, which exclusively represents this link. Then, the node numbers and the link numbers which have been set with respect to the respective intersections and the respective roads have been stored in digital map databases marketed by various firms in correspondence with both the node numbers and the link numbers.
Also, as to traffic information indicative of traffic jam positions, traffic accident positions, and the like, a link number is identified in order to represent a position on a road, and then, a point on the road is indicated by such an expression that this point is separated by a certain meter from a head portion of the road which is indicated by this link number. For example, in such a case that traffic information contains [position separated by 200 m from head portion of road of link number =“11113333”], even when on-vehicle navigation machines use any types of digital map databases, a position on the same road, namely a location indicated by the traffic information may be acquired by tracing such a location separated by 200 m from a node having a node number “1111” of the road defined by the link number “11113333.”
However, as shown in FIG. 58(b), as to node numbers and link numbers which have been defined in a road network, if a road “d” is newly constructed and the road is changed, then these numbers must be replaced by new numbers. When the node numbers and the link numbers are changed, digital map data of various firms must be updated.
Since constructions of roads and changes of roads are continuously carried out for the future, a plenty of work amounts and a great expense must be permanently required in order to perform maintenance operations of digital map databases as far as the conventional road position display method realized by the node numbers and the link numbers is utilized. Thus, there is such a problem that this maintenance operation is increased and causes heavy loads.
There is another method for identifying roads by way of shape matching system (will also be referred to as “map matching system”) based upon traffic information provided by the traffic information providing center 72. This shape matching system may largely depend upon processing performance of on-vehicle navigation machines provided on the reception side. As to a map matching operation executed in a conventional on-vehicle navigation machine, a matching process operation may be carried out one time every 1 second since only a map matching operation as to one place within a limited area (normally, square of several hundreds meters) around the own vehicle position is required. On the other hand, with respect to route lines (roads) which are to be processed in a traffic information providing system, normally, there are many roads such as speedways, national roads, and major local roads. Furthermore, in city areas, general roads belonging to the administrative divisions of Japan and a portion of city roads are involved in these route lines. Also, there are some possibilities that information acquiring route lines other than the existing links are increased.
As a consequence, the information processing capability of the conventional on-vehicle navigation machines owns such a problem that a plenty of time is required until a road is identified by executing a shape matching operation based upon received traffic information and then traffic information is displayed.
The present invention has been made to solve these problems, and has an object to provide a map matching method capable of realizing a high-speed process operation, and also, to provide an device and a computer program, which realize this map matching method. Furthermore, another object of the present invention is to provide a shape matching-purpose database and a shape matching device capable of providing positional information on a map while excessive maintenance operation for a map database is not performed. Also, another object of the present invention is to provide a shape matching-purpose database and a shape matching device, capable of quickly displaying, or representing information related to roads such as traffic information.